/*
 * Print the k most similar neighbor movies and their similarities for
 * each movie.
 *
 * First argument is k (number of neighbors).
 * Takes the matrix on standard in.
 * The matrix is required to have line breaks after each row.
 * Produces neighbors on standard out. Format is:
 * movie_id:neighbour_id similarity neighbour_id similarity ...
 * movie_id:neighbour_id similarity neighbour_id similarity ...
 * ...
 */
#include <algorithm>
#include <cassert>
#include <iostream>
#include <sstream>
#include <string>
#include "u1.h"

using namespace std;

struct F_neighbours
{
  const vector<double>& similarity;
  F_neighbours(const vector<double>& similarity) : similarity(similarity) { }
  bool operator()(size_t i, size_t j) const {
    // Want most similar elements at start of list.
    return similarity[i] > similarity[j];
  }
};

int main(int argc, char **argv)
{
  if (argc < 2) {
    cerr<<"See comments for usage."<<endl;
    return EXIT_FAILURE;
  }
  int k_in = atoi(argv[1]);
  if (k_in <= 0) {
    cerr<<"Number of neighbors, k, must be positive."<<endl;
    return EXIT_FAILURE;
  }
  size_t k = (size_t)k_in;

  // Don't lose too many digits when printing.
  cout.precision(8);

  string line;
  size_t row = 0, cols = -1U; // not portable, strictly speaking 
  vector<double> similarity;
  vector<size_t> pi;
  while (getline(cin,line)) {
    // Read row into vector. Put an "infinity" for the element on the diagonal.
    istringstream is(line);
    double entry;
    while (is >> entry) {
      if (row == similarity.size()) {
        similarity.push_back(DBL_MAX);
        continue;
      }
      similarity.push_back(entry);
    }

    // Sanity check: make sure all rows have same # of entries.
    if (cols == -1U) {
      cols = similarity.size();
      k = min(k, cols - 1);
    } else if (similarity.size() != cols) {
      cerr<<"Row "<<row+1<<" contains "<<similarity.size()<<" columns; expected "
        <<cols<<"."<<endl;
      exit(EXIT_FAILURE);
    }

    // Sort a permutation pi on the vector so that
    // similarity[pi[i]] > similarity[pi[i+1]]
    // That is, pi[0] is the most similar neighbor for this row.
    // It suffices to sort only the first k elements.
    for (size_t i = 0; i < similarity.size(); ++i)
      pi.push_back(i);
    sort(pi.begin(), pi.end(), F_neighbours(similarity));

    // We should always have the diagonal element in the 0th position.
    if (pi[0] != row) {
      cerr<<"Row "<<row<<" contains an infinity (not supported)."<<endl;
    }

    // Output neighbors. The first neighbour is just the current row.
    // Note that we capped k, above, so it will not be out of range.
    cout<<row+1<<":";
    for (size_t i = 1; i <= k; ++i) {
      assert(k < pi.size());
      cout<<pi[i]+1<<" "<<similarity[pi[i]]<<" ";
    }
    cout<<endl;

    // Prep for next row.
    similarity.clear();
    pi.clear();
    ++row;
  }

  return EXIT_SUCCESS;
}

/*
* Copyright (c) 2009 John Lees-Miller
* 
* Permission is hereby granted, free of charge, to any person
* obtaining a copy of this software and associated documentation
* files (the "Software"), to deal in the Software without
* restriction, including without limitation the rights to use,
* copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following
* conditions:
* 
* The above copyright notice and this permission notice shall be
* included in all copies or substantial portions of the Software.
* 
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
* OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
* NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
* HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
* WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
* OTHER DEALINGS IN THE SOFTWARE.
*/

